from typing import List


class Solution:
    def minCost(self, m: int, n: int, waitCost: List[List[int]]) -> int:
        inf = float('inf')
        dp = [[[inf for _ in range(2)] for _ in range(n)] for _ in range(m)]
        dp[0][0][1] = 1
        dp[0][0][0] = 1 + waitCost[0][0]
        for i in range(m):
            for j in range(n):
                if i > 0:
                    dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][1] + (i + 1) * (j + 1))
                if j > 0:
                    dp[i][j][0] = min(dp[i][j][0], dp[i][j - 1][1] + (i + 1) * (j + 1))
                dp[i][j][1] = min(dp[i][j][1], dp[i][j][0] + waitCost[i][j])
        return min(dp[m - 1][n - 1])


if __name__ == '__main__':
    s = Solution()
    r = s.minCost(m=1, n=2, waitCost=[[1, 2]])
    print(r)
